/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-24
 * Time: 6:22
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 最长无重复子串
 * 比较退格的字符串
 * 两个数组交集
 * 有效山脉
 * 移动0 删除重复项 有序数组平方
 * 二叉树的基本操作
 * 所有排序及优化
 */

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}
class Solution2 {

    public int preIndex =0;
    public int findPreIndex(int[] preorder, int[] inorder){
        for(int i =0;i<inorder.length;++i){
            if(preorder[preIndex]==inorder[i]){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildChildTree(int[] preorder, int[] inorder, int inbegin,int inend){
        if(inend<inbegin){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int ir = findPreIndex(preorder,inorder);
        preIndex++;
        if(ir==-1){
            return null;
        }
        root.left =buildChildTree(preorder,inorder,inbegin,ir-1);
        root.right =buildChildTree(preorder,inorder,ir+1,inend);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //前序遍历确定根节点，中序遍历确定左右子树
        return  buildChildTree(preorder,inorder,0,inorder.length-1);
    }
}

class Solution1 {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(ret==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        TreeNode cur = root;
        while(cur!=null){
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode top = stack.peek();
        if(top.right==null||top.right==prev){
            //左右都为空打印根
            stack.pop();
            ret.add(top.val);
            prev = top;
        }else {
            cur = top.right;
        }
        return ret;
    }
}

//class Solution4 {
//    public List<Integer> postorderTraversal(TreeNode root) {
//        List<Integer> ret = new ArrayList<>();
//        if(ret==null) return ret;
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode prev = null;
//        TreeNode cur = root;
//        while(cur!=null||(!stack.isEmpty())){
//            while(cur!=null){
//                stack.push(cur);
//                cur = cur.left;
//            }
//            TreeNode top = stack.peek();
//            if(top.right==null||top.right==prev){
//                //左右都为空打印根
//                stack.pop();
//                ret.add(top.val);
//                prev = top;
//            }else {
//                cur = top.right;
//            }
//        }
//        return ret;
//    }
//}

class Solution3 {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(ret==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null||(!stack.isEmpty())){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right==null||top.right!=prev){
                //左右都为空打印根
                stack.pop();
                ret.add(top.val);
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return ret;
    }
}

class Solution9 {
    public int lengthOfLongestSubstring(String s) {
        int start =0;
        int max = 0;
        for(int end =1;end<s.length();++end){
            int index = s.indexOf(start,s.charAt(end));
            if(index<end){
                start = index+1;
            }
            max = Math.max(max,end-start+1);
        }
        return max;
    }
}
public class TestDemo {

    public static int carFleet(int target, int[] pos, int[] speed) {
        int N = pos.length, res = 0;
        double[][] cars = new double[N][2];
        for (int i = 0; i < N; ++i)
            cars[i] = new double[] {pos[i], (double)(target - pos[i]) / speed[i]};
        Arrays.sort(cars, (a, b) -> Double.compare(a[0], b[0]));
        double cur = 0;
        for (int i = N - 1; i >= 0 ; --i) {
            if (cars[i][1] > cur) {
                cur = cars[i][1];
                res++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
      // solution.lengthOfLongestSubstring("abcabcbb");

    }

}
